package com.example.myletcodelearing.one

import java.util.*


/**
 * @author tgw
 * @date 2022/11/7
 *  * https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
 *
 *  输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
思路一：双指针 + 位运算
参数说明：

left：左指针
right：右指针
算法流程如下：

初始化左右指针指向数组两端
遍历数组，当 left >= right 即退出循环
指针 left 从左边开始，遇到奇数 left++，直到遇到偶数停止
指针 right 从右边开始，遇到偶数 right--，直到遇到奇数停止
交换左右指针
返回交互后的数组输出：[null,null,3,-1]
 */

fun main(args: Array<String>) {

    var op = Solution12.Solution()
//    var nums = arrayOf(1,  3, 5)
    var nums = arrayOf(1, 6, 3, 2, 5, 4, 7, 8, 9)
//    nums = op.exchange(nums)
//    nums = op.exchange2(nums)
//    nums = op.exChange5(nums)
    nums = op.exChange6(nums)

    for (element in nums) {
        println("奇数偶数：${element}")
    }


}

private class Solution12 {
    class Solution {
        /**
         * 左右指针
         */
        fun exchange(nums: Array<Int>): Array<Int> {
            var left = 0
            var right = nums.size - 1
            while (left < right) {
                // and == &
                while (left < right && nums[left] and 1 == 1) left++
                while (left < right && nums[right] and 1 != 1) right--

                if (left < right) {
                    // xor == ^
                    nums[left] = nums[left] xor nums[right]
                    nums[right] = nums[left] xor nums[right]
                    nums[left] = nums[left] xor nums[right]
                }
            }
            return nums;
        }

        /**
         *
         * 左边拿到偶数的下标，右边拿到基数的下标，然后两个数交换
         *
         * 注意交换的条件要左边的下标小于右边的下标，保证顺序
         * */
        fun exchange2(nums: Array<Int>): Array<Int> {
            var left = 0
            var right = nums.size - 1
            while (left < right) {
                while (left < right && nums[left] % 2 != 0) {
                    left++
                }

                while (left < right && nums[right] % 2 == 0) {
                    right--
                }

                if (left < right) {
                    val ou = nums[left]
                    val ji = nums[right]
                    nums[left] = nums[right]
                    nums[right] = ou
                    left++
                    right--
                }
            }
            return nums
        }


        /**
         * 快慢指针
         */
        fun exchange3(nums: Array<Int>): Array<Int> {
            var show = 0
            var fast = 0
            val size = nums.size
            while (fast < size) {
                // and == &
                if (nums[fast] % 2 != 0) {
                    val tmp = nums[show]
                    nums[show] = nums[fast];
                    nums[fast] = tmp;
                    show++
                }

                fast++
            }
            return nums;
        }

        /**
         *输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，
         * 所有偶数位于数组的后半部分，且相对位置不变

        示例 1：

        输入：nums = [1, 6, 3, 2, 5, 4, 7, 8, 9]
        输出：[1, 3, 5, 7, 9, 6, 2, 4, 8]

        这道题目重点在于「 奇数位于偶数前面，且相对位置不变 」，核心思路如下：

        遍历数组，记录第一次出现偶数的位置，记为 i
        接着从上一次偶数位置，继续遍历寻找奇数出现的位置，记录当前下标 j 和元素 temp
        移动数组 [i+1,j] 范围内的元素，统一向右移动 1 位
        将元素 temp 放到下标为 i 的位置上
         */

        //插入排序
        fun insertSort(nums: Array<Int>) {
            for (i in 1 until nums.size) {
                val temp = nums[i]
                var j = i - 1
                while (j >= 0 && nums[j] > temp) {
                    nums[j + 1] = nums[j]
                    j--
                }
                nums[j + 1] = temp
            }
        }


        //插入排序概念
        fun exChange5(nums: Array<Int>): Array<Int> {
            for (i in 0 until nums.size) {
                var temp = nums[i]
                var d = -1
                if (temp % 2 == 0) {
                    //找到了一个偶数
                    d = i
                    //从当前偶数开始遍历，找到一个基数
                    while (d < nums.size) {
                        //将从i到d-1的数整体向右移动，将奇数与前面的偶数一步步交换移动
                        if (nums[d] % 2 != 0) {
                            for (k in d downTo (i + 1)) {
                                var last = nums[k - 1]
                                nums[k - 1] = nums[k]
                                nums[k] = last
                            }
                            break
                        }
                        d++
                    }
                }
            }
            return nums
        }

        fun exChange6(nums: Array<Int>): Array<Int> {
            var i = 0
            while (i < nums.size) {
                var temp = nums[i]
                var d = -1
                if (temp % 2 == 0) {
                    //找到了一个偶数
                    d = i
                    //从当前偶数开始遍历，找到一个基数
                    while (d < nums.size) {
                        //将从i到d-1的数整体向右移动，将奇数与前面的偶数一步步交换移动
                        if (nums[d] % 2 != 0) {
                            for (k in d downTo (i + 1)) {
                                var last = nums[k - 1]
                                nums[k - 1] = nums[k]
                                nums[k] = last
                            }
                            break
                        }
                        d++
                    }
                }

                i++

            }
            return nums
        }

    }


}
